import java.util.LinkedList;
import java.util.Queue;

class Solution02 {
    // 定义数轴
    int[] dx = { 0, 0, -1, 1 };
    int[] dy = { 1, -1, 0, 0 };
    // 创建一个同规模的返回矩阵
    int[][] ret;
    int m, n;

    public int[][] updateMatrix(int[][] mat) {
        m = mat.length;
        n = mat[0].length;
        ret = new int[m][n];
        // 初始化为-1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret[i][j] =  -1;
            }
        }
        // 正难则反，找到里面的所有的0，向外扩展
        // 创建一个队列
        Queue<int[]> q = new LinkedList<>();
        // 遍历原始数组，入队
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 进行判断
                if (mat[i][j] == 0) {
                    ret[i][j] = 0;
                    q.add(new int[] { i, j });
                }
            }
        }
        // 循环判断
        while (!q.isEmpty()) {
            // 依次弹出队头元素
            int[] t = q.poll();
            int a = t[0], b = t[1];
            // 上下左右四个方向进行寻找
            for (int i = 0; i < 4; i++) {
                int x = a + dx[i], y = b + dy[i];
                // 进行判断
                if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1) {
                    // 先赋值，再添加到队列
                    ret[x][y] = ret[a][b] + 1;
                    // 入队
                    q.add(new int[]{x,y});
                }
            }
        }
        return ret;
    }
}